class Solution:
    def fourSum(self, nums, target):
        n = len(nums)
        if (not nums or n < 3):
            return []
        nums.sort()
        print(nums)
        res = []
        for i in range(n-3):
            print('i','n',i,n,'nums[i]',nums[i])
            if (i > 0 and nums[i] == nums[i - 1]):
                continue
            for j in range(n-1,2,-1):
                # print('j', j)
                if j < n-1 and nums[j] == nums[j+1]:
                    continue
                L = i + 1
                R = j - 1
                while L<R:
                    # print(L < R)
                    if (nums[i] + nums[j] + nums[L] + nums[R] == target):
                        res.append([nums[i],  nums[L], nums[R],nums[j]])
                        # print(L,L+1,R,R+1)
                        while (L < R and nums[L] == nums[L + 1]):
                            L = L + 1
                        while (L < R and nums[R] == nums[R - 1]):
                            R = R - 1
                        L += 1
                        R -= 1
                        print(L,R,'inner',L < R)
                    elif (nums[i] + nums[j] + nums[L] + nums[R] > target):
                        R -= 1
                    else:
                        L += 1
                    # print('Lend=', L, 'Rend=', R)
            # print(i)
            # i += 1
            # print('i', 'n', i, n)
        return res

print(Solution().fourSum([1,-2,-5,-4,-3,3,3,5],-11))
# class Solution:
#     def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
#         nums.sort()
#         n = len(nums)
#         res = []
#         p = 0 # p, k, i, j
#         while p < n - 3:  # 文中提到的条件1和条件2，可以直接跳过
#             if nums[p] + 3 * nums[p + 1] > target: break
#             if nums[p] + 3 * nums[-1] < target:
#                 while p < n - 4 and nums[p] == nums[p + 1]: p += 1
#                 p += 1
#                 continue
#             k = p + 1
#             while k < n - 2:   # k 和 p 的判断是一样的
#                 if nums[p] + nums[k] + 2 * nums[k + 1] > target: break
#                 if nums[p] + nums[k] + 2 * nums[-1] < target:
#                     while k < n - 3 and nums[k] == nums[k + 1]:
#                         k += 1
#                     k += 1
#                     continue
#                 i = k + 1
#                 j = n - 1
#                 new_target = target - nums[p] - nums[k]
#                 while i < j:
#                     if nums[i] + nums[j] > new_target: j -= 1
#                     elif nums[i] + nums[j] < new_target: i += 1
#                     else:
#                         res.append([nums[p],nums[k],nums[i],nums[j]])
#                         i += 1
#                         j -= 1
#                         while i < j and nums[i] == nums[i - 1]: i += 1 # 避免结果重复
#                         while i < j and nums[j] == nums[j + 1]: j -= 1 # 避免结果重复
#                 while k < n - 3 and nums[k] == nums[k + 1]: k += 1
#                 k += 1
#             while p < n - 4 and nums[p] == nums[p + 1]: p += 1
#             p += 1
#         return res
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        if (not nums or n < 3):
            return []
        nums.sort()
        res = []
        for i in range(n-3):
            if (i > 0 and nums[i] == nums[i - 1]):
                continue
            for j in range(n-1,2,-1):
                if j < n-1 and nums[j] == nums[j+1]:
                    continue
                L = i + 1
                R = j - 1
                while L<R:
                    if (nums[i] + nums[j] + nums[L] + nums[R] == target):
                        res.append([nums[i],  nums[L], nums[R],nums[j]])
                        while (L < R and nums[L] == nums[L + 1]):
                            L = L + 1
                        while (L < R and nums[R] == nums[R - 1]):
                            R = R - 1
                        L += 1
                        R -= 1
                    elif (nums[i] + nums[j] + nums[L] + nums[R] > target):
                        R -= 1
                    else:
                        L += 1
        return res
'''
更多的判重
'''
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        if n<4:return []
        res = []
        nums.sort()
        for i in range(n-3):
            if i >0 and nums[i] == nums[i-1]: continue
            for j in range(n-1,2,-1):
                if j<n-1 and nums[j] == nums[j+1]: continue
                L,R = i+1,j-1
                while L<R:
                    sums = nums[i] + nums[L] + nums[R] + nums[j]
                    if sums  == target:
                        res.append([nums[i] , nums[L] , nums[R] , nums[j]])
                        while L<R and nums[R] == nums[R-1]:
                            R-=1
                        while L<R and nums[L] == nums[L+1]:
                            L+=1
                        L += 1
                        R -= 1
                    elif sums > target:
                        while L<R and nums[R] == nums[R-1]:
                            R-=1
                        R -= 1
                    else:
                        while L<R and nums[L] == nums[L+1]:
                            L+=1
                        L += 1
        return res